"""
Problem 31: https://projecteuler.net/problem=31

In England the currency is made up of pound, £, and pence, p, and there are
eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/11
'''

recalltimes1 = 0


def count1(Money: int = 200, charges: list = [1, 2, 5, 10, 20, 50, 100, 200]) -> int:
    '''

    S(M,8) = sum(
                    S(M-c8*0, 7),
                    S(M-c8*1, 7),
                    S(M-c8*2, 7),
                    ...
                    S(M-c8*k, 7)
                )
    where c8 = 200, k = M//c8

    driectly compute using recursion


    >>> assert count1(1) == 1
    >>> assert count1(5) == 4
    >>> assert count1(9) == 8
    '''
    global recalltimes1
    recalltimes1 += 1

    # print(Money, charges)

    if Money == 0:
        return 1
    else:
        if not charges:
            return 0
        else:
            charges.sort()
            if len(charges) == 1:
                return 0 if Money % charges[0] else 1

    return sum([count1(m, charges[:-1])
                for m in range(Money, -1, -1*charges[-1])])


# *****************************************************************

Data = dict()
recalltimes2 = 0


def count2(Money: int = 200, charges: list = [1, 2, 5, 10, 20, 50, 100, 200]) -> int:
    '''
    compute using recursion, but save tmp result to a dict DATA

    >>> assert count2(1) == 1
    >>> assert count2(5) == 4
    >>> assert count2(9) == 8
    '''
    global Data
    global recalltimes2
    recalltimes2 += 1

    if (Money, *charges) in Data:
        return Data[(Money, *charges)]

    if Money == 0:
        Data[(Money, *charges)] = 1
        return 1
    else:
        if not charges:
            Data[(Money, *charges)] = 0
            return 0
        else:
            charges.sort()
            if len(charges) == 1:
                if Money % charges[0]:
                    Data[(Money, *charges)] = 0
                    return 0
                else:
                    Data[(Money, *charges)] = 1
                    return 1

    Data[(Money, *charges)] = sum([count2(Money - i*charges[-1], charges[:-1]) for i in range(
        Money//charges[-1] + 1)])
    return Data[(Money, *charges)]


# *****************************************************************


def count3(Money: int = 200, charges: list = [1, 2, 5, 10, 20, 50, 100, 200]) -> int:
    '''
    not use recursion, compute S(M,8) from m=0 to m=M

    >>> print(count3(1))
    1
    >>> print(count3(5))
    4
    >>> print(count3(9))
    8
    '''
    charges = [0] + charges
    res = [[0]*len(charges) for _ in range(Money+1)]
    for cs in range(len(charges)):
        res[0][cs] = 1

    for m in range(1, Money+1):
        for cs in range(1, len(charges)):
            res[m][cs] = sum([res[i][cs-1]
                             for i in range(m, -1, -1*(charges[cs]))])

    return res[Money][len(charges)-1]


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print('count1(): ', count1())
    # 73682
    print(f'func count1() is recalled {recalltimes1} times.')
    # 76995

    print('count2(): ', count2())
    # 73682
    print(f'func count2() is recalled {recalltimes2} times.')
    # 2786
    print('Data: ', len(Data))
    # 312

    print('count3(): ', count3())
    # 1133873304647601

    print('OK!')

    '''
    count3() is more effective, which can compute larger Money.
    '''
